package com.fjh.algorithm.thought.dpointer;

/**
 * @Author FJH
 * @Date 2021/6/1 11:20
 * @Desc Trapping Rain Water 接雨水
 */
public class TrappingRainWater {

    /**
     * leetcode 42.接雨水 - 双指针法
     * <p>
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
     * 计算按此排列的柱子，下雨之后能接多少雨水。
     */
    public static int trap(int[] height) {
        if (height.length == 0) return 0;
        int left = 0, right = height.length - 1; // 左右指针
        int leftMax = 0, rightMax = 0; // 左右指针最大值
        int result = 0;
        while (left <= right) {
            if (leftMax < rightMax) { // 每次移动其中最短的那根指针向中间移动。
                if (leftMax > height[left]) {
                    // 如果左挡板 > 左指针指向高度，则能接到（leftMax - height[left]）雨水
                    result += leftMax - height[left];
                } else {
                    // 如果左挡板 <= 左指针指向高度，则把左挡板高度换成左指针指向高度
                    leftMax = height[left];
                }
                // 左指针右移
                left++;
            } else {
                if (rightMax > height[right]) {
                    // 如果右挡板 > 右指针指向高度，则能接到（rightMax - height[right]）雨水
                    result += rightMax - height[right];
                } else {
                    // 如果右挡板 <= 右指针指向高度，则把右挡板高度换为右指针指向高度
                    rightMax = height[right];
                }
                // 右指针左移
                right--;
            }
        }
        return result;
    }


    /**
     * leetcode 407.接雨水2
     * <p>
     * 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，
     * 请计算图中形状最多能接多少体积的雨水。
     */
    public static int trap2(int[][] heightMap) {
        return 0;
    }

    /**
     * 京东笔试题 接雨水2plus
     * <p>
     * 京东笔试题,力扣上没有原题,但是和接雨水2类似,只是最后求的不是总雨水的数量,
     * 而是最后区域内留了多少雨水积水区,
     * 如接雨水2中的题目,答案就是两块积水区.
     */
    public static int trap2plus(int[][] heightMap) {
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

}
